locations = [2,3,6,8,4]
start = 1
finish = 3
fuel = 5

# locations = [4,3,1]
# start = 1
# finish = 0
# fuel = 6

# locations = [5,2,1]
# start = 0
# finish = 2
# fuel = 3

# locations = [2,1,5]
# start = 0
# finish = 0
# fuel = 3

# locations = [1,2,3]
# start = 0
# finish = 2
# fuel = 40
###代码超时
def dfs(locations,start,finish,fuel,path,res,is_reach):
    #出口条件
    if start==finish and not is_reach:
        #到达目标城市
        print("++++++++++++到达了目的城市+++++++++++++++")
        print(path)
        # res.append(path[:])
        res[0]+=1
        if fuel>min(locations[:start]+locations[start+1:]):
            dfs(locations,start,finish,fuel,path,res,True)
        print("++++++++++++++++++++++++++++++++++++++")
        return None
    if fuel<=0 or fuel<min(locations[:start]+locations[start+1:]):
        print("==========================一次递归完成....,没有到达目标城市==========")
        print(path)
        print("=====================================================")
        #没有达到目标城市，且当前的油量也不足以去其他的城市了
        return None
    is_reach=False
    for i in range(len(locations)):
        if i!=start and fuel>=abs(locations[start]-locations[i]):
            #要去的城市不能是当前城市,并且汽油量足够我们到达
            path.append(i)
            print(path)
            print("当前可到达的城市是：",i)
            print("汽油剩余量:",fuel-abs(locations[start]-locations[i]))
            dfs(locations,i,finish,fuel-abs(locations[start]-locations[i]),path,res,is_reach)
            path.pop()
def countRoutes(locations, start, finish, fuel):
    #存放结果
    res=[0]
    path=[]
    is_reach=False
    dfs(locations,start,finish,fuel,path,res,is_reach)
    print(res[0])
countRoutes(locations,start,finish,fuel)